package reviewAlgorithms.dynamicProgramming;

import java.util.ArrayList;
import java.util.List;

public class WordBreak {
    public static void main(String[] args) {
        List<String> wordDict = new ArrayList<>();
        wordDict.add("apple");
        wordDict.add("pen");
        wordDict.add("sand");
        wordDict.add("and");
        wordDict.add("cat");
        String s = "applepenapple";
        System.out.println(wordBreak(s,wordDict));
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() < 1){
            return false;
        }
        if (wordDict == null || wordDict.size() < 1){
            return false;
        }
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 0; j < i ; j++) {
                if (dp[j] && check(s.substring(j,i),wordDict)){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    private static boolean check(String str, List<String> wordDict) {
        if (str.length() < 1){
            return true;
        }

        return wordDict.contains(str);
    }
}
